/*
    * Copyright 2004-2005, University Health Network.  All rights reserved. Distributed under the BSD 
    * license (see http://opensource.org/licenses/bsd-license.php).
    *  
    * Created on 9-Dec-2004
    */
   package ca.uhn.cache.impl;
   
   import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Iterator;
  import java.util.List;
  
  import org.apache.commons.logging.Log;
  import org.apache.commons.logging.LogFactory;
  import org.springframework.beans.factory.InitializingBean;
  
  import ca.uhn.cache.IDimension;
  import ca.uhn.cache.IParamSpace;
  import ca.uhn.cache.IQuery;
  import ca.uhn.cache.IQueryParam;
  import ca.uhn.cache.internal.IParamSpaceConfig;
  
  /***
   * A multi-dimensional space of <code>IQueryParam</code>s.  A data item 
   * has a location in this space (see <code>IDataInspector</code>).  Data 
   * items are divided into <code>IChunk</code>s that represent regions of the 
   * space.  
   *   
   * @author <a href="mailto:bryan.tripp@uhn.on.ca">Bryan Tripp</a>
   * @version $Revision: 1.1 $ updated on $Date: 2005/01/24 22:52:39 $ by $Author: bryan_tripp $
   */
  public class ParamSpace implements IParamSpace, InitializingBean {
  
      private static final Log ourLog = LogFactory.getLog( ParamSpace.class );
      
      private IParamSpaceConfig myParamSpaceConfig;
      
      /***
       * Factory method.
       * 
       * @param theParamSpaceConfig The configuration information for this space (defining dimensions, etc).
       * @return The created <code>ParamSpace</code>. 
       */
      public static ParamSpace createInstance( IParamSpaceConfig theParamSpaceConfig ) {
          ParamSpace retVal = new ParamSpace();
          
          retVal.setParamSpaceConfig(theParamSpaceConfig);
          
          return retVal;
      }
  
      /***
       */
      public ParamSpace() {
      }
      
      /***
       * {@inheritDoc}
       */
      public IDimension[] getDimensions()
      {
          return myParamSpaceConfig.getDimensions();
      }
      
      /***
       * {@inheritDoc}
       */
      public IQueryParam[] chunk(IQueryParam theParam)
      {
          IQueryParam[] result = null;
      
          if (myParamSpaceConfig.isChunked(theParam.getDimension())) {
              IQueryParam[] all = myParamSpaceConfig.getChunkBoundaries(theParam.getDimension()); 
              
              List intersecting = new ArrayList(); 
              for (int i = 0; i < all.length; i++) {
                  if (theParam.intersects(all[i])) {
                      intersecting.add(all[i]);
                  } 
              }
  
              //TODO: should maybe check whether the result spans the original param as well as whether 
              //there is no intersection (don't have a way to do this currently)
              if (intersecting.size() == 0) {
                  ourLog.warn("An IQueryParam intersects 0 chunks.  ParamSpace may not be configured properly");
              }
              
              result = (IQueryParam[]) intersecting.toArray(new IQueryParam[ intersecting.size() ]);
          } else {
              //TODO: should maybe warn if we don't have a point param.  Range/set params won't 
              //necessarily be consistent across calls, so chunk lookup won't work.  Consequence: 
              //missed cache hits, unused cached data. 
              result = new IQueryParam[] {theParam};
          }
  
          return result;
      }
  
     /***
      * {@inheritDoc}
      */
     public IQuery[] group( IQuery[] theQueries, int theMaxGroups ) {
         IQuery[] retVal = theQueries;
         
         if ( theMaxGroups > 0 ) {
             do {
                 retVal = doGroup(retVal, theMaxGroups);
             } while (retVal.length > theMaxGroups);
         }
         
         return retVal;
     }
     
     //a single pass through a list of IQuery to group them  
     private IQuery[] doGroup(IQuery[] theQueries, int theMaxGroups) {
         List grouped = new ArrayList(theQueries.length);
         List ungrouped = new ArrayList(Arrays.asList(theQueries));
         
         while (ungrouped.size() > 0 && (grouped.size() + ungrouped.size()) > theMaxGroups) {
             IQuery toGroup = (IQuery) ungrouped.remove(0);
             IQuery closestGrouped = findClosest(toGroup, grouped);
             IQuery closestUngrouped = findClosest(toGroup, ungrouped);
             
             if (isCloser(toGroup, closestUngrouped, closestGrouped)) {
                 ungrouped.remove(closestUngrouped);
                 grouped.add(merge(toGroup, closestUngrouped));
             } else {
                 grouped.remove(closestGrouped);
                 grouped.add(merge(toGroup, closestGrouped));                
             }
         }                
         
         grouped.addAll(ungrouped);
         return (IQuery[]) grouped.toArray(new IQuery[0]);
     }
     
     //compares distances from one query to two others, treating distance to null
     //query as infinity 
     private boolean isCloser(IQuery theFrom, IQuery theTo, IQuery theOtherTo) {        
         if (theTo == null) {
             return false;
         } else if (theOtherTo == null) {
             return true;
         } else {
             return (distance(theFrom, theTo) < distance(theFrom, theOtherTo)) ? true : false; 
         }
     }
     
     //results in union of two queries PLUS all space between 
     private IQuery merge(IQuery theQuery, IQuery theOther) {
         Query result = new Query();
 
         if (theQuery.getParameters().size() != theOther.getParameters().size()) {
             throw new IllegalArgumentException("Can't merge queries with different "
                     + "numbers of dimensions");
         }
         
         Iterator params = theQuery.getParameters().iterator();
         while (params.hasNext()) {
             IQueryParam oneParam = (IQueryParam) params.next();
             IQueryParam otherParam = getParam(theOther, oneParam.getDimension());
             result.addParameter(oneParam.merge(otherParam));
         }
         
         return result;
     }
     
     //finds closest query in a list 
     //TODO: can optimize by defining a minimum distance below which grouping 
     //is considered good enough (don't have to find global optimim)
     private IQuery findClosest(IQuery theQuery, List theQueries) {
         float shortestDistance = 10000f;
         IQuery closest = null;
         
         for (int i = 0; i < theQueries.size(); i++) {
             float distance = distance(theQuery, (IQuery) theQueries.get(i));
             if (distance < shortestDistance) {
                 shortestDistance = distance;
                 closest = (IQuery) theQueries.get(i);
             }
         }
         
         return closest;
     }
     
     //TODO: could be optimized if IQuery had getParameter(IDimension)
     private float distance(IQuery theQuery, IQuery theOtherQuery) {
         float squaredResult = 0;
         
         Iterator params = theQuery.getParameters().iterator();
         while (params.hasNext()) {
             IQueryParam oneParam = (IQueryParam) params.next();
             IQueryParam otherParam = getParam(theOtherQuery, oneParam.getDimension());
             float distance = oneParam.getDistance(otherParam, 
                     myParamSpaceConfig.getSaturationPoint(oneParam.getDimension()));
             squaredResult += (distance * distance);
         }
         
         return (float) Math.sqrt(squaredResult);
     }
     
     //returns the IQueryParam in the given dimension (exception if missing)
     private IQueryParam getParam(IQuery theQuery, IDimension theDimension) {
         IQueryParam result = null;
         
         Iterator params = theQuery.getParameters().iterator();
         while (params.hasNext() && result == null) {
             IQueryParam param = (IQueryParam) params.next();
             if (param.getDimension().equals(theDimension)) {
                 result = param;
             }
         }
         
         if (result == null) {
             throw new IllegalArgumentException("Query has no parameter of dimension "
                     + theDimension.getName());
         }
         
         return result;
     }
     
     ////////// SPRING BEGIN /////////
 
     /***
      * @return The configuration information for this space (defining dimensions, etc).
      */
     public IParamSpaceConfig getParamSpaceConfig() {
         return myParamSpaceConfig;
     }
     /***
      * @param theConfigData The configData to set.
      */
     public void setParamSpaceConfig( IParamSpaceConfig theConfigData ) {
         myParamSpaceConfig = theConfigData;
     }
 
     /***
      * {@inheritDoc}
      */
     public void afterPropertiesSet() throws Exception {
         assert getParamSpaceConfig() != null : "getParamSpaceConfig() != null";
     }
     
     ////////// SPRING END /////////
     
     
 }